package 滑动窗口;

import java.util.HashMap;
import java.util.HashSet;

public class 水果成篮5 {
    //https://leetcode.cn/problems/fruit-into-baskets/submissions/666574144/
    public int totalFruit1(int[] fruits) {
        HashMap<Integer,Integer> map = new HashMap<>();
        int left = 0, right = 0, ret = 0;
        while (right < fruits.length) {
            /*if(!map.containsKey(fruits[right])) {
                map.put(fruits[right],1);
            }else {
                map.put(fruits[right],map.get(fruits[right]) + 1);
            }*/
            map.put(fruits[right],map.getOrDefault(fruits[right],0) + 1);
            while (map.size() > 2) {
                map.put(fruits[left],map.get(fruits[left]) - 1);
                if(map.get(fruits[left]) == 0) {
                    map.remove(fruits[left]);
                }
                left++;
            }
            ret = Math.max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
    public int totalFruit(int[] fruits) {
        int n = fruits.length;
        int[] hash = new int[n]; // 每个元素统计此种水果的个数
        int ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < n; right++) {
            if(hash[fruits[right]] == 0) {
                kinds++; // 维护水果种类个数
            }
            hash[fruits[right]]++; // 进窗口
            while (kinds > 2) {
                hash[fruits[left]]--; // 出窗口
                if(hash[fruits[left]] == 0) {
                    kinds--;
                }
                left++;
            }
            // 更新结果
            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }
}
